import BST, { BstNode } from "..";
import { print } from "../../AVL/test";
import { print2 } from "../test";

export { };

const inOrder = <T = number>(bst: BST<T>) => {
    const root = bst.getRoot();

    if (root === null) return;

    let p = root;

    /**
     * 寻找前驱节点
     * @param n 
     */
    const getAced = (n: BstNode<T>) => {
        // 从左子节点开始
        let left = n.left;

        while (left && left.right !== null && left.right !== n) {
            // 一直往右边找
            left = left.right;
        }

        return left!;

    }

    // 循环遍历
    while (p !== null) {
        if (p.left !== null) {
            // 存在左子树, 找该节点的前驱节点, 其right指向自己
            const aced = getAced(p);

            // 右子节点为空
            if (aced.right === null) {
                aced.right = p;

                // 重新改变p的指向 
                p = p.left;
            } else if (aced.right === p) {

                // 访问该节点
                console.log(p.value);

                // 将前驱节点的right清空, 恢复二叉树的性质
                aced.right = null

                p = p.right!;
            }



        } else {
            // 左子树为空, 遍历该元素, 重新指向p为其右子树
            console.log(p.value);

            p = p.right!;

        }
    }

}


/**
 * 前序遍历
 * @param bst 
 */
const preOrder = <T = number>(bst: BST<T>) => {
    const root = bst.getRoot();

    // 拷贝一份
    let p = bst.copy();

    /**
     * 获取前驱节点
     * @param n 
     */
    const getAced = (n: BstNode<T>) => {
        // 从左子节点开始
        let left = n.left;

        // 一直找到右为空
        while(left && left.right !== null) {
            left = left.right;
        }

        return left;
    }   


    while (p !== null) {
        if (p.left !== null) {
            // 范文该节点
            console.log(p.value);

            // 找到p的前驱节点, 其指向p.right
            const aced = getAced(p)!

            // 前驱节点的right指向p.right 
            aced.right = p.right;
            
            // p重新指向 p.left
            p = p.left;
        } else {
            // 左子节点为空, 访问, p重新指向p.right
            console.log(p.value);

            // p 重新指向 p.right
            p = p.right;
        }
    }
}


/**
 * 后序遍历
 * @param bst 
 */
const postOrder = <T = number>(bst: BST<T>) => {
    const root = bst.getRoot();

    if (root === null) return

    let p = root;

    /**
     * 获取前驱节点
     * @param n 
     */
    const getAced = (n: BstNode<T>) => {
        let left = n.left;

        // 一直找到right为空
        while(left && left.right !== null && left.right !== n) {
            left = left.right;
        }

        return left;
    }

    /**
     * 逆序 a.right = b  b.right = c  => c.right = b, b.right = a, a.right = null 
     * @param from 
     */
    const reverseNode = (n: BstNode<T>) => {
        let prev = null,
            next = null;
        
        while (n !== null) {
            // 下一个
            next = n.right;

            n.right = prev;

            // 之前的
            prev = n;

            n = next!
        }    

        return prev
    }

    /**
     * 逆序打印n
     * @param n 
     */
    const printNode = (n: BstNode<T>) => {
        let r = reverseNode(n)!,
            // 保存, 用于恢复
            r2 = r;

        // 打印
        while(r !== null) {
            console.log(r.value);
            r = r.right!;
        }

        // 恢复树
        reverseNode(r2)
    }

    while(p !== null) {
        if (p.left !== null) {
            const aced = getAced(p)!;

            if (aced.right === null) {
                // 令right指向p
                aced.right = p;

                // 重新改变p的指向
                p = p.left;
            } else if (aced.right === p) {
                //! 先将right清空, 然后再访问 

                // 恢复原来的二叉树
                aced.right = null;


                // 访问节点
                printNode(p.left)


                // p 指向p.right
                p = p.right!;
            }

        } else {
            // 左子节点为空, 指向其右孩子
            p = p.right!;
        }
    }

    printNode(root);
}


const bst = new BST();

bst.batchAdd([70, 87, 16, 46, 34, 2, 1, 27, 32, 90, 89, 17]);
// debugger
// inOrder(bst);
// preOrder(bst);
print2(bst.getRoot())
postOrder(bst)
print2(bst.getRoot())